/**
 * Consider the fraction, p/q, where p and q are positive integers. If p < q 
 * and gcd(p,q)=1, it is called a reduced proper fraction.
 *
 * If we list the set of reduced proper fractions for q <= 8 in ascending order
 * of value, we get:
 *
 *   1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 
 *   5/7, 3/4, 4/5, 5/6, 6/7, 7/8
 *
 * It can be seen that there are 21 elements in this set.
 *
 * How many elements would be contained in the set of reduced proper fractions 
 * for q <= 1,000,000?
 *
 * SOLUTION: Let phi(n) be the totient function of n. Then the answer is 
 * phi(2)+phi(3)+...+phi(1,000,000). We use a Sieve method to find the totient
 * function value of all the n.
 *
 * ANSWER: 303963552391.
 */

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>
#include "prime.h"
#include "farey.h"

void solve_problem_72()
{
#if 0
	const int M = 30000;
#else
	const int M = 1000000;
#endif

#if 0
	farey_sequence<int> f(M);
	// std::copy(f.begin(), f.end(), std::ostream_iterator<fraction<int>>(std::cout, "\n"));
	std::cout << std::distance(f.begin(), f.end()) - 2 << std::endl;
#elif 1
	farey_sequence<int> f(M);
	std::cout << f.size()-2 << std::endl;
#else
	std::vector<int> phi(M+1);
	totient(phi);
	long long sum = std::accumulate(phi.cbegin()+2, phi.cend(), 0LL);
	std::cout << sum << std::endl;
#endif
}
